﻿//给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
//选择某个下标 i 并将 nums[i] 替换为 - nums[i] 。
//重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
//以这种方式修改数组后，返回数组 可能的最大和 。
//
//输入：nums = [4, 2, 3], k = 1
//输出：5
//解释：选择下标 1 ，nums 变为[4, -2, 3] 。
//
//输入：nums = [3, -1, 0, 2], k = 3
//输出：6
//解释：选择下标(1, 2, 2) ，nums 变为[3, 1, 0, 2] 。
//
//输入：nums = [2, -3, -1, 5, -4], k = 2
//输出：13
//解释：选择下标(1, 4) ，nums 变为[2, 3, -1, 5, 4] 。
//
//提示：
//	1 <= nums.length <= 10^4
//	- 100 <= nums[i] <= 100
//	1 <= k <= 10^4

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m = 0, minElem = INT_MAX, n = nums.size();
        for (auto x : nums) {
            if (x < 0)
                m++;
            minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数
        }
        // 分类讨论
        int ret = 0;
        if (m > k) {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++) // 前k⼩个负数，变成正数
            {
                ret += -nums[i];
            }
            for (int i = k; i < n; i++) // 后⾯的数不变
            {
                ret += nums[i];
            }
        }
        else {
            // 把所有的负数变成正数

            for (auto x : nums)
                ret += abs(x);
            if ((k - m) % 2) // 判断是否处理最⼩的正数
            {
                ret -= minElem * 2;
            }
        }
        return ret;
    }
};